#!/bin/python
import sys, os, random, heapq, operator, collections, math, copy, re# simanneal_simple #, profile, mycheck

in_file_name = None
out_file_name = None
n = 0
m = 0
problem = None

Pc = 0.9
#Pm = 0.1


Operation = collections.namedtuple('Operation', ['time', 'job_id', 'machine_id', 'duration'])
Candidate = collections.namedtuple('Candidate', ['objective', 'permutation', 'schedule'])
Interval = collections.namedtuple('Interval', ['start', 'end'])


def copy_candidate(candidate):
    """ Copies a solution candidate
    """
    permutation_copy = []
    for i in candidate.permutation:
        permutation_copy.append(i)

    schedule_copy = []
    for resource in candidate.schedule:
        resource_copy = []
        for job in resource:
            resource_copy.append(Operation(job.time, job.job_id, job.machine_id, job.duration))
        schedule_copy.append(resource_copy)
    return Candidate(candidate.objective, permutation_copy, schedule_copy)


def take(slack, position, duration):
    """ Returns 2 slacks created by pushing a job into one slack.
    """
    if not fits(slack, position, duration):
        raise ArithmeticError
    slacks = []
    if position > slack.start:
        slacks.append(Interval(slack.start, position))
    if position + duration < slack.end:
        slacks.append(Interval(position + duration, slack.end))
    return slacks


def fits(slack, position, duration):
    """ Returns true if the operation fits to this slack.
    """
    return position + duration <= slack.end


def create_problem(infile):
    """ Puts all the job/resource combinations into a list
        and initializes global parameters
    """
    global n, m, problem
    problem_description = infile.readline()
    n, m = infile.readline().split()
    n = int(n)
    m = int(m)
    problem = []
    for job_id, line in enumerate(infile):
        if not line.isspace():
            line_iter = iter(line.split())
            sequence = []
            for r in xrange(m):
                machine_id = int(line_iter.next())
                duration = int(line_iter.next())
                operation = Operation(None, job_id, machine_id, duration)
                sequence.append(operation)
            problem.append(sequence)


def random_candidate2():
    """ Creates a random solution candidate
    """
    permutation = [i for i in xrange(n)]
    random.shuffle(permutation)
    schedule = pack(permutation)
    return Candidate(objective(schedule), permutation, schedule)

def random_candidate():
    myproblem = copy.deepcopy(problem)
    generators = [collections.deque(myproblem[i]) for i in xrange(n)]
    schedule = [list() for j in xrange(m)]
    est = [0 for i in xrange(n)]
    resource_gaps = [[Interval(0, sys.maxint)] for j in xrange(m)]
    while len(generators) > 0:
        r1 = random.randrange(len(generators))
        g = generators[r1]
        job = g.popleft()
        if len(g) == 0:
            generators.remove(g)
        gaps = resource_gaps[job.machine_id]
        resource = schedule[job.machine_id]
        for idx, gap in enumerate(gaps):
            t = max(est[job.job_id], gap.start)
            if fits(gap, t, job.duration):
                resource_gaps[job.machine_id] = gaps[0:idx] + take(gap, t, job.duration) + gaps[idx + 1:]
                resource.append(Operation(t, job.job_id, job.machine_id, job.duration))
                est[job.job_id] = t + job.duration
                break

    schedule = [sorted(resource) for resource in schedule]
    return Candidate(objective(schedule), [job.job_id for job in schedule[random.randrange(m)]], schedule)


def pack(permutation):
    """ Takes a permutation and creates a schedule for all the ops.
        Needs to be refactored for speed.
    """
    append = list.append
    resource_slacks = [ [Interval(0, sys.maxint) ] for j in xrange(m)]
    est = [0 for i in xrange(n)]
    machines = [list() for j in xrange(m)]
    for i in permutation:
        sequence = problem[i]
        for job in sequence:
            slacks = resource_slacks[job.machine_id]
            resource = machines[job.machine_id]
            for idx, slack in enumerate(slacks):
                t = max(est[job.job_id], slack.start)
                if fits(slack, t, job.duration):
                    resource_slacks[job.machine_id] = slacks[0:idx] + take(slack, t, job.duration) + slacks[idx + 1:]
                    append(resource, Operation(t, job.job_id, job.machine_id, job.duration))
                    est[job.job_id] = t + job.duration
                    break
    return [sorted(resource) for resource in machines]


def neighbors(p):
    ne = []
    for i in xrange(1, n - 1):
        copy = p[:]
        copy[i], copy[i + 1] = copy[i + 1], copy[i]
        ne.append(copy)
    return ne


def walk(candidate):
    best = candidate
    while True:
        schedules = [(q, pack(q)) for q in neighbors(best.permutation)]
        candidates = [Candidate(objective(schedule), q, schedule) for q, schedule in schedules]
        good = max(candidates)
        if good.objective < best.objective:
            best = copy_candidate(good)
            continue
        else:
            return best


def makespan(candidate):
    """ Cmax or makespan """
    return max(map(lambda operation: operation.time + operation.duration, map(operator.itemgetter(-1), candidate)))

def twft(candidate):
    """ Total weighted flow time """
    return sum(map(lambda operation: operation.time + operation.duration, map(operator.itemgetter(-1), candidate)))


def order1(l1, l2):
    """ Order 1 permutation operator
    """
    k = random.randrange(len(l1))
    f = [elt for idx, elt in enumerate(l1) if idx < k]
    return f + [elt for elt in l2 if elt not in f]

def pairs(l1, l2):
    offspring = []
    d1 = collections.deque(l1)
    d2 = collections.deque(l2)
    while len(d1) > 0 or len(d2) > 0:
        if len(d1) >= 2:
            a = d1.popleft()
            b = d1.popleft()
            offspring.extend((a,b))
            if a in d2:
                d2.remove(a)
            if b in d2:
                d2.remove(b)
        if len(d2) >= 2:
            a = d2.popleft()
            b = d2.popleft()
            offspring.extend((a,b))
            if a in d1:
                d1.remove(a)
            if b in d1:
                d1.remove(b)
    return offspring


def crossover_candidate(candidate1, candidate2):
    cross_operator = order1
    """ Create 2 offsprings by crossover """
    offsprings = []
    for i in xrange(2):
        permutation = cross_operator(candidate1.permutation, candidate2.permutation)
        schedule = pack(permutation)
        offsprings.append(Candidate(objective(schedule), permutation, schedule))
        candidate1, candidate2 = candidate2, candidate1
    return tuple(offsprings)

def select(candidates):
    """ Tournament selection.
    """
    selection = []
    for i in xrange(len(candidates) - 1):
        selection.append(max(candidates[i], candidates[i + 1]))
    while len(selection) < len(candidates):
        selection.append(candidates[random.randrange(len(candidates))])
    return selection

def simple_genetic_algorithm(problem):
    """ Rothlauf: Algorithm 7 Simple Genetic Algorithm
    """
    N = (m + n)
    random_population = [random_candidate() for i in xrange(N)]
    best = max(random_population)
    print '%s (random)' % best.objective
    heapq.heapify(random_population)
    not_improved = 0
    max_ni = (m + n)
    while not_improved < max_ni:
        improved = False
        for i in xrange(N - 1):
            if random.random() <= Pc:
                offspring1, offspring2 = crossover_candidate(random_population[i], random_population[i + 1])
                heapq.heappush(random_population, offspring1)
                heapq.heappush(random_population, offspring2)
                crossover_best = max([best, offspring1, offspring2])
                if (crossover_best.objective < best.objective):
                    best = copy_candidate(crossover_best)
                    print '%s (crossover)' % best.objective
                    improved = True
                    not_improved = 0
            Pm = math.exp(-(N / ((not_improved + 1) * N / max_ni)))
            #print not_improved, ': ', round(Pm, 2),
            perm = random_population[i].permutation
            changed = False
            for l in xrange(len(perm) - 1):
                if random.random() <= Pm:
                    changed = True
                    r = random.randrange(len(perm))
                    perm[l], perm[r] = perm[r], perm[l]
            if changed:
                schedule = pack(perm)
                cost = objective(schedule)
                mutant = Candidate(cost, perm, schedule)
                heapq.heappush(random_population, mutant)
                if (cost < best.objective):
                    best = Candidate(mutant.objective, mutant.permutation, mutant.schedule)
                    print '%s (mutate)' % best.objective
                    improved = True
                    not_improved = 0
        random_population = heapq.nsmallest(N, random_population)
        if not improved:
            not_improved += 1
    return best


def save(best, cycle):
    print best.objective, ' ', cycle
    record_data(best)
    return
    """ Saves a schedule
    """
    with open(out_file_name, 'w') as out_file:
        out_file.write(str(makespan(best.schedule)) + ' ' + str(twft(best.schedule)) + '\n')
        for resource in best.schedule:
            for op in resource:
                out_file.write(str(op.job_id) + ' ' + str(op.time) + ' ')
            out_file.write('\n')


def record_data(best):
    fname = copy.copy(in_file_name)
    fname = re.sub('cs540-jsp/', '', fname)
    fname = re.sub('.inst.txt', '', fname)
    fname = re.sub('.txt', '', fname)
    with open("mucsi-khaki.csv", 'a') as exp:
        exp.write('%s,%s\n' % (fname, best.objective))


def pretty_print(candidate):
    """ Pretty print
    """
    overlap = []
    for resource in candidate:
        time = 0
        for idx, job in enumerate(resource):
            if job.time < time:
                overlap.append((resource[idx-1], job))
            while job.time > time:
                sys.stdout.write(' ')
                time += 1
            for i in xrange(job.duration):
                sys.stdout.write(str(job.job_id))
                time += 1
        sys.stdout.write('\n')
    print '(%s)' % objective(candidate)
    print overlap


if __name__ == '__main__':
    if len(sys.argv) == 4:
        program_name, in_file_name, out_file_name, obj_function = sys.argv
    else:
        print 'Program requires 3 arguments: <input_file>, <output_file>, <objective function{0,1}>'
        os._exit(0)
    if obj_function == '0':
        objective = makespan
    elif obj_function == '1':
        objective = twft
    else:
        objective = makespan

    with open(in_file_name) as in_file:
        create_problem(in_file)
    #profile.run('save(simple_genetic_algorithm(problem), "final")')
    #save(simple_genetic_algorithm(problem), "final")
    best = random_candidate()
    for i in range(1000):
        asolution = simple_genetic_algorithm(problem)
        if asolution.objective < best.objective:
            best = copy_candidate(asolution)
            record_data(best)
